/*
 * Quercia Luciano
 * Algoritmi e Strutture Dati
 * a.a. 2009-10
 */


#ifndef ALBERO_H_
#define ALBERO_H_

#include <iostream>
using namespace std;

#define NDEBUG
#include <cassert>

#include "nodoAn.h"

template <class T>
class Albero {

public:

	typedef typename NodoAn<T>::posizione posizione;

	Albero();
	~Albero();

	void creaAlbero();
	bool alberoVuoto();
	posizione radice()				throw (char const *) ;
	posizione padre( posizione )	throw (char const *) ;
	posizione primoFiglio( posizione )	throw (char const *) ;
	posizione fratelloDestro( posizione )	throw (char const *) ;
	bool ultimoFratello( posizione )	throw (char const *) ;
	bool foglia( posizione )		throw (char const *) ;

	void insRadice()				throw (char const *);
	void insRadice( T )				throw (char const *);

	void insPrimoFiglio( posizione )	throw (char const *);
	void insPrimoFiglio( posizione, T )	throw (char const *);

	void insFratelloDestro( posizione )	throw (char const *);
	void insFratelloDestro( posizione, T )	throw (char const *);

	void cancSottoAlbero( posizione )	throw (char const *);

	T leggiNodo( posizione )		throw (char const *);
	void scriviNodo( posizione, T )	throw (char const *);

	//operatori personalizzati
	void print();
	void print( posizione );

private:
	posizione root;

};




//DEFINIZIONE

template <class T>
Albero<T>::Albero() {
	creaAlbero();
}

template <class T>
Albero<T>::~Albero() {
	if ( ! alberoVuoto() )
		cancSottoAlbero( root );
}


template <class T>
void Albero<T>::creaAlbero() {
	root = NULL;
}



template <class T>
bool Albero<T>::alberoVuoto() {
	return ( root == NULL );
}

template <class T>
typename Albero<T>::posizione Albero<T>::radice() throw (char const *) {
	if ( !alberoVuoto() )
		return root;
	else
		throw "Albero Vuoto.";
}


template <class T>
typename Albero<T>::posizione Albero<T>::padre( posizione p ) throw (char const *) {
	if ( !alberoVuoto() )
		if ( p != NULL )
			if ( p != radice() )
				return p->getPadre();
			else
				throw "La radice non ha padre.";
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}


template <class T>
typename Albero<T>::posizione Albero<T>::primoFiglio( posizione p ) throw (char const *) {
	if ( !alberoVuoto() )
		if ( p != NULL )
			if ( p->getPrimoFiglio() != NULL )
				return p->getPrimoFiglio();
			else
				throw "Il nodo non ha figli.";
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}


template <class T>
typename Albero<T>::posizione Albero<T>::fratelloDestro( posizione p ) throw (char const *) {
	if ( !alberoVuoto() )
		if ( p != NULL )
			if ( p->getFratelloDestro() != NULL )
				return p->getFratelloDestro();
			else
				throw "Il nodo non ha fratello destro.";
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}

template <class T>
bool Albero<T>::ultimoFratello( posizione p ) throw (char const *) {
	if ( !alberoVuoto() )
		if ( p != NULL )
			if ( ! ( p->getFratelloDestro() == NULL ) )
				return true;
			else
				return false;
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}


template <class T>
bool Albero<T>::foglia( posizione p ) throw (char const *) {
	if ( !alberoVuoto() )
		if ( p != NULL )
			if ( p->getPrimoFiglio() == NULL )
				return true;
			else
				return false;
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}


template <class T>
void Albero<T>::insRadice() throw (char const *) {
	if ( alberoVuoto() )
		root = new NodoAn<T>;
	else
		throw "Albero non vuoto.";
}

template <class T>
void Albero<T>::insRadice( T elem ) throw (char const *) {
	insRadice();
	scriviNodo( root, elem );
}


template <class T>
void Albero<T>::insPrimoFiglio( posizione p ) throw (char const *) {
	if ( ! alberoVuoto() )
		if ( p != NULL )
			if ( p->getPrimoFiglio() == NULL ) {

				posizione temp = new NodoAn<T>;
				temp->setPadre(p);
				temp->setPrimoFiglio( NULL );
				temp->setFratelloDestro( NULL );

				p->setPrimoFiglio( temp );
			}
			else
				throw "Il nodo ha già un figlio.";
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}


template <class T>
void Albero<T>::insPrimoFiglio( posizione p, T elem ) throw (char const *) {
	insPrimoFiglio( p );
	scriviNodo( p->getPrimoFiglio(), elem );
}


template <class T>
void Albero<T>::insFratelloDestro( posizione p ) throw (char const *) {
	if ( ! alberoVuoto() )
		if ( p != NULL )
			if ( p->getFratelloDestro() == NULL ) {
				posizione temp = new NodoAn<T>;
				temp->setPadre( p->getPadre() );
				temp->setPrimoFiglio( NULL );
				temp->setFratelloDestro( NULL );

				p->setFratelloDestro( temp );
			}
			else
				throw "Il nodo ha già un fratello destro.";
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}


template <class T>
void Albero<T>::insFratelloDestro( posizione p, T elem ) throw (char const *) {
	insFratelloDestro( p );
	scriviNodo( p->getFratelloDestro(), elem );
}




template <class T>
void Albero<T>::cancSottoAlbero( posizione p ) throw (char const *) {
	if ( ! alberoVuoto() )
		if ( p != NULL ) {
			while ( !foglia(p) )
				cancSottoAlbero( p->getPrimoFiglio() );
			if ( p != radice() )
				p->getPadre()->setPrimoFiglio( p->getFratelloDestro() );
			else
				root = NULL;
			delete p;
		}
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}



template <class T>
T Albero<T>::leggiNodo( posizione p ) throw (char const *) {
	if ( !alberoVuoto() )
		if ( p != NULL )
			return p->getValue();
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}


template <class T>
void Albero<T>::scriviNodo( posizione p, T elem ) throw (char const *) {
	if ( !alberoVuoto() )
		if ( p != NULL )
			p->setValue(elem);
		else
			throw "Posizione non valida.";
	else
		throw "Albero vuoto.";
}



template <class T>
void Albero<T>::print() {
	if ( alberoVuoto() )
		cout << "[Empty]" << endl;
	else
		print( root );
}

template <class T>
void Albero<T>::print( posizione p ) {
	cout << p->getValue();
	if ( foglia(p) )
		return;
	cout << " (";
	posizione q = p->getPrimoFiglio();
	while ( q != NULL ) {
		cout << " ";
		print(q);
		cout << " ";
		q = q->getFratelloDestro();
	}
	cout << ")";
}


#endif /* MAIN_CPP_ */
